/*
 * @lc app=leetcode.cn id=491 lang=cpp
 *
 * [491] 递增子序列
 */

// @lc code=start
class Solution
{
private:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int> &nums, int index)
    {
        //几个条件
        // 1:递增 2 子序列 3 不重复
        //终止条件
        if (path.size() >= 2)
        {
            res.push_back(path);
            // return;这里是寻找所有结果所以不返回
        }
        //需要用set去重
        //也可以用数组去重  相当于哈希 因为给定了范围
        unordered_set<int> st;
        for (int i = index; i < nums.size(); i++)
        {
            if (!path.empty() && nums[i] < path.back())
            {
                //不符合递增
                continue;
            }
            if (st.find(nums[i]) != st.end())
            {
                //去重
                continue;
            }
            st.insert(nums[i]); //该元素本层不能在使用
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> findSubsequences(vector<int> &nums)
    {
        //递增子序列
        backtracking(nums, 0);
        return res;
    }
};
// @lc code=end

